package airthmetic.exercise.recursion;

public class _10_正则表达式匹配 {

    public boolean isMatch(String s, String p) {
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        return recur(ss,0,pp,0);
    }

    public boolean recur(char[] s, int i, char[] p, int j){
        if(p.length == j){
            return s.length == i;
        }

        boolean isMatch = i < s.length && (s[i] == p[j] || p[j] == '.');
        if(p.length - j >= 2 && p[j+1] == '*'){
            return recur(s,i,p,j+2) || (isMatch && recur(s,i+1,p,j));
        }
        return isMatch && recur(s,i+1,p,j+1);
    }
}
